package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-01-01 18:31
 **/
public class LeetCode338 {

    //动态规划-最低有效位
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            //bits[i >> 1] + i & 1的含义就是找到自身除以2所包含的bit数,然后如果是奇数就+1,偶数不加。
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }


    //Brian Kernighan 算法
    /*public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = countOnes(i);
        }
        return res;
    }

    int countOnes(int num) {
         int count = 0;
         while (num > 0) {
             num &= num - 1;
             ++count;
         }
         return count;
    }*/

    //api
    /*public int[] countBits(int n) {
        int[] res = new int[n + 1];
        int i = 0;
        while (i <= n) {
            res[i] = Integer.bitCount(i);
            ++i;
        }
        return res;
    }*/

}
